#include<unordered_map>
#include<set>
#include<vector>
#include<iostream>
#include <vector>
#include <random>
#include <chrono>

class RandomizedCollection
{
public:
    std::unordered_map<int, std::set<int>> my_map;
    std::vector<int> my_vector;

    RandomizedCollection()
    {
    }

    bool insert(int val)
    {
        //查重
        bool flag = find(val);
        
        //插入
        int n = my_vector.size();
        my_vector.push_back(val);
        if (flag)
        {
           
            my_map[val].insert(n);
        }
        else
        {
            if (my_map.find(val) == my_map.end())
            {
                my_map.insert({val,{n}});
            }
            else
            {
                my_map[val].insert(n);
            }
        }
        return !flag;
    }

    bool find(int key)
    {
        if (my_map.find(key) == my_map.end())
        {
            return false;
        }
        else
        {
            if (my_map[key].empty())
            {
                return false;
            }else
            {
                return true;
            }
        }
    }


    bool remove(int val)
    {
       bool flag = find(val);
        if (flag)
        {
            
            int index = *my_map[val].begin();
            my_map[val].erase(index);
            
            int n = static_cast<int>(my_vector.size());
            if (index==n-1)
            {
                my_vector.pop_back();
                my_map[val].erase(index);
            }
            else
            {
                int value = my_vector[n-1];
                my_map[value].erase(n-1);
                my_map[value].insert(index);
                my_vector.pop_back();
                my_vector[index] = value;
            }
         
        }
       
        return flag;
    }

   
int getRandom() {
      
    
        // 使用梅森旋转算法作为随机数引擎
        static std::mt19937 generator(
            std::chrono::system_clock::now().time_since_epoch().count()
        );
    
        // 创建一个均匀分布
        std::uniform_int_distribution<size_t> distribution(0, my_vector.size() - 1);
    
        // 生成随机索引并返回元素
        return my_vector[distribution(generator)];
    }

    void sout()
    {
        for (int vector : my_vector)
        {
            std::cout << vector << " ";
        }
    }
};

